#include <iostream>
using namespace std;

long long fibonacci(int n) {
	if (n <= 1)
		return n;
	
	long long f1 = 0, f2 = 1, f3 = 0;
	for (int i=2; i<=n; i++) {
		f3 = f1 + f2;

		f1 = f2;
		f2 = f3;
	}

	return f3;
}

//int main() {
//	long long rt = fibonacci(5000);
//	return 0;
//}